//运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 
//
// 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 
//写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在
//写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 
//
// 
//
// 进阶: 
//
// 你是否可以在 O(1) 时间复杂度内完成这两种操作？ 
//
// 
//
// 示例: 
//
// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1);       // 返回  1
//cache.put(3, 3);    // 该操作会使得关键字 2 作废
//cache.get(2);       // 返回 -1 (未找到)
//cache.put(4, 4);    // 该操作会使得关键字 1 作废
//cache.get(1);       // 返回 -1 (未找到)
//cache.get(3);       // 返回  3
//cache.get(4);       // 返回  4
// 
// Related Topics 设计


package leetcode.d_100_199;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

// 请查看 code.lru.LRUCache!!!
//Java：LRU缓存机制
public class P146LruCache{
    public static void main(String[] args) {
        //Solution solution = new P146LruCache().new Solution();
        // TO TEST
    }

    class LRUCache {
        int capacity;
        Map<Integer, Integer> cache;
        LinkedList<Integer> list;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>();
            this.list = new LinkedList<>();
        }

        public int get(int key) {
            // 如果存在则返回，并将key放到链表最头部
            // 如果不存在则返回-1
            if (cache.containsKey(key)) {
                int value = cache.get(key);
                this.makeRecently(key);
                return value;
            }
            return -1;
        }

        public void put(int key, int value) {
            // 如果存在，则更新，并将key放到链表最头部
            // 如果不存在，则判断容量，并插入，并将key放到链表最头部
            if (!cache.containsKey(key)) {
                if (cache.size() >= this.capacity) {
                    this.removeOldst();
                }
                cache.put(key, value);
                this.list.addFirst(key);
                return;
            }
            cache.put(key, value);
            this.makeRecently(key);
        }

        private void makeRecently(int key) {
            Integer k = key;
            this.list.remove(k);
            this.list.addFirst(key);
        }

        private void removeOldst() {
            // 删除最尾部的节点
            int key = this.list.removeLast();
            cache.remove(key);
        }
    }

}